#ifndef BALANCETREE_H
#define BALANCETREE_H

#include <algorithm>
#include <iostream> 
using namespace std;


class UnderflowException { };
class IllegalArgumentException { };
class ArrayIndexOutOfBoundsException { };
class IteratorOutOfBoundsException { };
class IteratorMismatchException { };
class IteratorUninitializedException { };

// AvlTree class
//
// CONSTRUCTION: zero parameter
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x (unimplemented)
// bool contains( x )     --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as warranted

template <typename Comparable>
class AvlTree
{
 public:
 AvlTree( ) : root{ nullptr }{ }
    
 AvlTree( const AvlTree & rhs ) : root{ nullptr }{
    root = clone( rhs.root );
  }

 AvlTree( AvlTree && rhs ) : root{ rhs.root }{
    rhs.root = nullptr;
  }
    
  ~AvlTree( ){
      makeEmpty( );
    }

  /**
   * Deep copy.
   */
  AvlTree & operator=( const AvlTree & rhs ){
      AvlTree copy = rhs;
      std::swap( *this, copy );
      return *this;
    }
        
  /**
   * Move.
   */
  AvlTree & operator=( AvlTree && rhs ){
      std::swap( root, rhs.root );
        
      return *this;
    }
    
  /**
   * Find the smallest item in the tree.
   * Throw UnderflowException if empty.
   */
  const Comparable & findMin( ) const{
    if( isEmpty( ) )
      throw UnderflowException{ };
    return findMin( root )->element;
  }

  /**
   * Find the largest item in the tree.
   * Throw UnderflowException if empty.
   */
  const Comparable & findMax( ) const{
    if( isEmpty( ) )
      throw UnderflowException{ };
    return findMax( root )->element;
  }

  /**
   * Returns true if x is found in the tree.
   */
  bool contains( const Comparable & x ) const{
    return contains( x, root );
  }

  /**
   * Test if the tree is logically empty.
   * Return true if empty, false otherwise.
   */
  bool isEmpty( ) const{
    return root == nullptr;
  }

  /**
   * Print the tree contents in sorted order.
   */
  void printTree( ) const{
    if( isEmpty( ) )
      cout << "Empty tree" << endl;
    else
      printTree( root );
  }

  /**
   * Make the tree logically empty.
   */
  void makeEmpty( )
  {
    makeEmpty( root );
  }

  /**
   * Insert x into the tree; duplicates are ignored.
   */
  void insert( const Comparable & x ){
    insert( x, root );
  }
     
  /**
   * Insert x into the tree; duplicates are ignored.
   */
  void insert( Comparable && x ){
    insert( std::move( x ), root );
  }
     
  /**
   * Remove x from the tree. Nothing is done if x is not found.
   */
  void remove( const Comparable & x ){
    remove( x, root );
  }

 private:
  struct AvlNode
  {
    Comparable element;
    AvlNode   *left;
    AvlNode   *right;
    int       height;

  AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 )
  : element{ ele }, left{ lt }, right{ rt }, height{ h } { }
        
  AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0 )
  : element{ std::move( ele ) }, left{ lt }, right{ rt }, height{ h } { }
  };

  AvlNode *root;


  /**
   * Internal method to insert into a subtree.
   * x is the item to insert.
   * t is the node that roots the subtree.
   * Set the new root of the subtree.
   */
  void insert( const Comparable & x, AvlNode * & t ){
    if( t == nullptr )
      t = new AvlNode{ x, nullptr, nullptr };
    else if( x < t->element )
      insert( x, t->left );
    else if( t->element < x )
      insert( x, t->right );
        
    balance( t );
  }

  /**
   * Internal method to insert into a subtree.
   * x is the item to insert.
   * t is the node that roots the subtree.
   * Set the new root of the subtree.
   */
  void insert( Comparable && x, AvlNode * & t )
  {
    if( t == nullptr )
      t = new AvlNode{ std::move( x ), nullptr, nullptr };
    else if( x < t->element )
      insert( std::move( x ), t->left );
    else if( t->element < x )
      insert( std::move( x ), t->right );
        
    balance( t );
  }
     
  /**
   * Internal method to remove from a subtree.
   * x is the item to remove.
   * t is the node that roots the subtree.
   * Set the new root of the subtree.
   */
  void remove( const Comparable & x, AvlNode * & t ){
    if( t == nullptr )
      return;   // Item not found; do nothing
        
    if( x < t->element )
      remove( x, t->left );
    else if( t->element < x )
      remove( x, t->right );
    else if( t->left != nullptr && t->right != nullptr ) // Two children
      {
	t->element = findMin( t->right )->element;
	remove( t->element, t->right );
      }
    else
      {
	AvlNode *oldNode = t;
	t = ( t->left != nullptr ) ? t->left : t->right;
	delete oldNode;
      }
        
    balance( t );
  }
    
  static const int ALLOWED_IMBALANCE = 1;

  // Assume t is balanced or within one of being balanced
  void balance( AvlNode * & t ){
    if( t == nullptr )
      return;
        
    if( height( t->left ) - height( t->right ) > ALLOWED_IMBALANCE )
      if( height( t->left->left ) >= height( t->left->right ) )
	rotateWithLeftChild( t );
      else
	doubleWithLeftChild( t );
    else
      if( height( t->right ) - height( t->left ) > ALLOWED_IMBALANCE )
	if( height( t->right->right ) >= height( t->right->left ) )
	  rotateWithRightChild( t );
	else
	  doubleWithRightChild( t );
                
    t->height = max( height( t->left ), height( t->right ) ) + 1;
  }
    
  /**
   * Internal method to find the smallest item in a subtree t.
   * Return node containing the smallest item.
   */
  AvlNode * findMin( AvlNode *t ) const{
    if( t == nullptr )
      return nullptr;
    if( t->left == nullptr )
      return t;
    return findMin( t->left );
  }

  /**
   * Internal method to find the largest item in a subtree t.
   * Return node containing the largest item.
   */
  AvlNode * findMax( AvlNode *t ) const
  {
    if( t != nullptr )
      while( t->right != nullptr )
	t = t->right;
    return t;
  }


  /**
   * Internal method to test if an item is in a subtree.
   * x is item to search for.
   * t is the node that roots the tree.
   */
  bool contains( const Comparable & x, AvlNode *t ) const{
    if( t == nullptr )
      return false;
    else if( x < t->element )
      return contains( x, t->left );
    else if( t->element < x )
      return contains( x, t->right );
    else
      return true;    // Match
  }
  /****** NONRECURSIVE VERSION*************************
	  bool contains( const Comparable & x, AvlNode *t ) const
	  {
	  while( t != nullptr )
	  if( x < t->element )
	  t = t->left;
	  else if( t->element < x )
	  t = t->right;
	  else
	  return true;    // Match

	  return false;   // No match
	  }
  *****************************************************/

  /**
   * Internal method to make subtree empty.
   */
  void makeEmpty( AvlNode * & t )
  {
    if( t != nullptr )
      {
	makeEmpty( t->left );
	makeEmpty( t->right );
	delete t;
      }
    t = nullptr;
  }

  /**
   * Internal method to print a subtree rooted at t in sorted order.
   */
  void printTree( AvlNode *t ) const{
    if( t != nullptr )
      {
	printTree( t->left );
	cout << t->element << endl;
	printTree( t->right );
      }
  }

  /**
   * Internal method to clone subtree.
   */
  AvlNode * clone( AvlNode *t ) const{
    if( t == nullptr )
      return nullptr;
    else
      return new AvlNode{ t->element, clone( t->left ), clone( t->right ), t->height };
  }
  // Avl manipulations
  /**
   * Return the height of node t or -1 if nullptr.
   */
  int height( AvlNode *t ) const
  {
    return t == nullptr ? -1 : t->height;
  }

  int max( int lhs, int rhs ) const
  {
    return lhs > rhs ? lhs : rhs;
  }

  /**
   * Rotate binary tree node with left child.
   * For AVL trees, this is a single rotation for case 1.
   * Update heights, then set new root.
   */
  void rotateWithLeftChild( AvlNode * & k2 ){
    AvlNode *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
    k1->height = max( height( k1->left ), k2->height ) + 1;
    k2 = k1;
  }

  /**
   * Rotate binary tree node with right child.
   * For AVL trees, this is a single rotation for case 4.
   * Update heights, then set new root.
   */
  void rotateWithRightChild( AvlNode * & k1 ){
    AvlNode *k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = max( height( k1->left ), height( k1->right ) ) + 1;
    k2->height = max( height( k2->right ), k1->height ) + 1;
    k1 = k2;
  }

  /**
   * Double rotate binary tree node: first left child.
   * with its right child; then node k3 with new left child.
   * For AVL trees, this is a double rotation for case 2.
   * Update heights, then set new root.
   */
  void doubleWithLeftChild( AvlNode * & k3 ){
    rotateWithRightChild( k3->left );
    rotateWithLeftChild( k3 );
  }

  /**
   * Double rotate binary tree node: first right child.
   * with its left child; then node k1 with new right child.
   * For AVL trees, this is a double rotation for case 3.
   * Update heights, then set new root.
   */
  void doubleWithRightChild( AvlNode * & k1 ){
    rotateWithLeftChild( k1->right );
    rotateWithRightChild( k1 );
  }
};



// SplayTree class
//
// CONSTRUCTION: with no parameters
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// bool contains( x )     --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// bool isEmpty( )        --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as warranted

template <typename Comparable>
class SplayTree
{
 public:
  SplayTree( )
    {
      nullNode = new BinaryNode;
      nullNode->left = nullNode->right = nullNode;
      root = nullNode;
    }

  SplayTree( const SplayTree & rhs )
    {
      nullNode = new BinaryNode;
      nullNode->left = nullNode->right = nullNode;
      root = clone( rhs.root );
    }

 SplayTree( SplayTree && rhs ) : root{ rhs.root }, nullNode{ rhs.nullNode }{
    rhs.root = nullptr;
    rhs.nullNode = nullptr;
  }
    
  ~SplayTree( ){
      makeEmpty( );
      delete nullNode;
    }

    
  /**
   * Deep copy.
   */
  SplayTree & operator=( const SplayTree & rhs ){
      SplayTree copy = rhs;
      std::swap( *this, copy );
      return *this;
    }
        
  /**
   * Move.
   */
  SplayTree & operator=( SplayTree && rhs ){
      std::swap( root, rhs.root );
      std::swap( nullNode, rhs.nullNode );
        
      return *this;
    }
    
  /**
   * Find the smallest item in the tree.
   * Not the most efficient implementation (uses two passes), but has correct
   *     amortized behavior.
   * A good alternative is to first call find with parameter
   *     smaller than any item in the tree, then call findMin.
   * Return the smallest item or throw UnderflowException if empty.
   */
  const Comparable & findMin( ){
    if( isEmpty( ) )
      throw UnderflowException{ };

    BinaryNode *ptr = root;

    while( ptr->left != nullNode )
      ptr = ptr->left;

    splay( ptr->element, root );
    return ptr->element;
  }

  /**
   * Find the largest item in the tree.
   * Not the most efficient implementation (uses two passes), but has correct
   *     amortized behavior.
   * A good alternative is to first call find with parameter
   *     larger than any item in the tree, then call findMax.
   * Return the largest item or throw UnderflowException if empty.
   */
  const Comparable & findMax( ){
    if( isEmpty( ) )
      throw UnderflowException{ };

    BinaryNode *ptr = root;

    while( ptr->right != nullNode )
      ptr = ptr->right;

    splay( ptr->element, root );
    return ptr->element;
  }


  bool contains( const Comparable & x ){
    if( isEmpty( ) )
      return false;
    splay( x, root );
    return root->element == x;
  }

  bool isEmpty( ) const{
    return root == nullNode;
  }

  void printTree( ) const{
    if( isEmpty( ) )
      cout << "Empty tree" << endl;
    else
      printTree( root );
  }

  void makeEmpty( ){
    /******************************
     * Comment this out, because it is prone to excessive
     * recursion on degenerate trees. Use alternate algorithm.
        
        reclaimMemory( root );
        root = nullNode;
    *******************************/
    while( !isEmpty( ) )
      {
	findMax( );        // Splay max item to root
	remove( root->element );
      }
  }

  void insert( const Comparable & x )
  {
    static BinaryNode *newNode = nullptr;

    if( newNode == nullptr )
      newNode = new BinaryNode;
    newNode->element = x;

    if( root == nullNode )
      {
	newNode->left = newNode->right = nullNode;
	root = newNode;
      }
    else
      {
	splay( x, root );
	if( x < root->element )
	  {
	    newNode->left = root->left;
	    newNode->right = root;
	    root->left = nullNode;
	    root = newNode;
	  }
	else
	  if( root->element < x )
            {
	      newNode->right = root->right;
	      newNode->left = root;
	      root->right = nullNode;
	      root = newNode;
            }
	  else
	    return;
      }
    newNode = nullptr;   // So next insert will call new
  }

  void remove( const Comparable & x )
  {
    // If x is found, it will be splayed to the root by contains
    if( !contains( x ) )
      return;   // Item not found; do nothing

    BinaryNode *newTree;

    if( root->left == nullNode )
      newTree = root->right;
    else
      {
	// Find the maximum in the left subtree
	// Splay it to the root; and then attach right child
	newTree = root->left;
	splay( x, newTree );
	newTree->right = root->right;
      }
    delete root;
    root = newTree;
  }

 private:
  struct BinaryNode
  {
    Comparable  element;
    BinaryNode *left;
    BinaryNode *right;

  BinaryNode( ) : left{ nullptr }, right{ nullptr } { }
        
  BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
  : element{ theElement }, left{ lt }, right{ rt } { }       
  };
    
  BinaryNode *root;
  BinaryNode *nullNode;

  /**
   * Internal method to reclaim internal nodes in subtree t.
   * WARNING: This is prone to running out of stack space.
   */
  void reclaimMemory( BinaryNode * t )
  {
    if( t != t->left )
      {
	reclaimMemory( t->left );
	reclaimMemory( t->right );
	delete t;
      }
  }
    
  /**
   * Internal method to print a subtree t in sorted order.
   * WARNING: This is prone to running out of stack space.
   */
  void printTree( BinaryNode *t ) const
  {
    if( t != t->left )
      {
	printTree( t->left );
	cout << t->element << endl;
	printTree( t->right );
      }
  }

  /**
   * Internal method to clone subtree.
   * WARNING: This is prone to running out of stack space.
   */
  BinaryNode * clone( BinaryNode * t ) const
  {
    if( t == t->left )  // Cannot test against nullNode!!!
      return nullNode;
    else
      return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) };
  }

  // Tree manipulations
  void rotateWithLeftChild( BinaryNode * & k2 )
  {
    BinaryNode *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2 = k1;
  }

  void rotateWithRightChild( BinaryNode * & k1 )
  {
    BinaryNode *k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1 = k2;
  }

  /**
   * Internal method to perform a top-down splay.
   * The last accessed node becomes the new root.
   * This method may be overridden to use a different
   * splaying algorithm, however, the splay tree code
   * depends on the accessed item going to the root.
   * x is the target item to splay around.
   * t is the root of the subtree to splay.
   */
  void splay( const Comparable & x, BinaryNode * & t )
  {
    BinaryNode *leftTreeMax, *rightTreeMin;
    static BinaryNode header;

    header.left = header.right = nullNode;
    leftTreeMax = rightTreeMin = &header;

    nullNode->element = x;   // Guarantee a match

    for( ; ; )
      if( x < t->element )
	{
	  if( x < t->left->element )
	    rotateWithLeftChild( t );
	  if( t->left == nullNode )
	    break;
	  // Link Right
	  rightTreeMin->left = t;
	  rightTreeMin = t;
	  t = t->left;
	}
      else if( t->element < x )
	{
	  if( t->right->element < x )
	    rotateWithRightChild( t );
	  if( t->right == nullNode )
	    break;
	  // Link Left
	  leftTreeMax->right = t;
	  leftTreeMax = t;
	  t = t->right;
	}
      else
	break;

    leftTreeMax->right = t->left;
    rightTreeMin->left = t->right;
    t->left = header.right;
    t->right = header.left;
  }
};



#endif
